package com.kevin.Code.DP;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname PartitionEqualSubsetSum
 * @Description Leetcode 416. 分割等和子集 中等难度  动态规划背包问题
 * @Date 2021/10/8 21:27
 * @Version 1.0
 */
public class PartitionEqualSubsetSum {


    /**
     * 转化成0-1背包问题
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {

        int len = nums.length;

        if (len == 1) {
            return false;
        }

        int sum = 0;
        int target = 0;
        int maxNum = 0;

        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
            sum = sum + num;
        }


        //如果总数不能够分为两部分，则返回false
        if (sum % 2 != 0) {
            return false;
        }
        target = sum / 2;

        //如果最大的值大于总数的一半，则返回false
        if (maxNum > target) {
            return false;
        }

        //1.明确状态和转移条件

        //2.明确dp数组的定义
        boolean[][] dp = new boolean[len + 1][target + 1];

        for (int i = 1; i <= len; i++) {

            //base case有点难以理解
            //背包没有空间表示背包已经装满
            dp[i][0] = true;

            for (int j = 1; j <= target; j++) {
                //3.确定动态转移方程
                //如果剩下的容量不足以装下，则取决于
                if (j - nums[i - 1] < 0) {
                    //如果当前i个数不能够组成和为j的子集，则取决于i-1的数是否能够组成和为j的子集
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //如果不将当前的数装入子集中，则容量为j的自己能否组成子集取决i-1个数能否组成
                    //装入该数，则是否能够组成取决于前i-1数是否能够组成和为j-nums[i]的子集
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }


        return dp[len][target];
    }

    public static void main(String[] args) {
        PartitionEqualSubsetSum partitionEqualSubsetSum = new PartitionEqualSubsetSum();
        int[] nums = new int[]{1, 5, 11, 5};
        boolean b = partitionEqualSubsetSum.canPartition(nums);
        System.out.println(b);
    }
}
